﻿#define _CRT_SECURE_NO_WARNINGS 1
//typedef int DataType;
//class StackInt
//{
//public:
//	StackInt(size_t capacity = 3)
//	{
//		_array = (DataType*)malloc(sizeof(DataType) * capacity);
//		if (NULL == _array)
//		{
//			perror("malloc申请空间失败!!!");
//			return;
//		}
//
//		_capacity = capacity;
//		_size = 0;
//	}
//
//	void Push(DataType data)
//	{
//		// CheckCapacity();
//		_array[_size] = data;
//		_size++;
//	}
//
//	// 其他方法...
//
//	~StackInt()
//	{
//		if (_array)
//		{
//			free(_array);
//			_array = NULL;
//			_capacity = 0;
//			_size = 0;
//		}
//	}
//
//private:
//	DataType* _array;
//	int _capacity;
//	int _size;
//};
//
//typedef double DataType;
//class StackDouble
//{
//public:
//	StackDouble(size_t capacity = 3)
//	{
//		_array = (DataType*)malloc(sizeof(DataType) * capacity);
//		if (NULL == _array)
//		{
//			perror("malloc申请空间失败!!!");
//			return;
//		}
//
//		_capacity = capacity;
//		_size = 0;
//	}
//
//	void Push(DataType data)
//	{
//		// CheckCapacity();
//		_array[_size] = data;
//		_size++;
//	}
//
//	// 其他方法...
//
//	~StackDouble()
//	{
//		if (_array)
//		{
//			free(_array);
//			_array = NULL;
//			_capacity = 0;
//			_size = 0;
//		}
//	}
//
//private:
//	DataType* _array;
//	int _capacity;
//	int _size;
//};
//
//int main()
//{
//	StackInt s1; // int
//	StackDouble s2; // double
//	return 0;
//}
//	template<class T>
//	class Stack
//	{
//	public:
//		Stack(size_t capacity = 3);
//
//		void Push(const T& data);
//
//		// 其他方法...
//
//		~Stack()
//		{
//			if (_array)
//			{
//				free(_array);
//				_array = NULL;
//				_capacity = 0;
//				_size = 0;
//			}
//		}
//
//	private:
//		T* _array;
//		int _capacity;
//		int _size;
//	};
//
//
//	template<class T>
//	Stack<T>::Stack(size_t capacity)
//	{
//		/*_array = (T*)malloc(sizeof(T) * capacity);
//		if (NULL == _array)
//		{
//			perror("malloc申请空间失败!!!");
//			return;
//		}*/
//		_array = new T[capacity];
//
//		_capacity = capacity;
//		_size = 0;
//	}
//
//	template<class T>
//	void Stack<T>::Push(const T& data)
//	{
//		// CheckCapacity();
//		_array[_size] = data;
//		_size++;
//	}
//
//int main()
//{
//	string s1;
//	string s2("张三");
//	string s3("hello worldasdadwdasdawsda");
//	string s4(10, '*');
//	string s5(s2);
//
//		s1 = s2;
//		cout << s1 << endl;
//	
//		s1 = "1111";
//		cout << s1 << endl;
//	
//		s1 = '2';
//		cout << s1 << endl;
//	
//		return 0;
//}
//int main()
//{
//	vector<int> v;
//	v.push_back(1);
//	v.push_back(2);
//	v.push_back(3);
//	v.push_back(4);
//	list<int> lt;
//	lt.push_back(10);
//	lt.push_back(20);
//	lt.push_back(3);
//	lt.push_back(4);
//	reverse(v.begin(), v.end());
//	reverse(lt.begin(), lt.end());
//	for (auto e : v)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//
//	for (auto e : lt)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//
//}
//void Func(const string& s)
//{
//	string::iterator it = s.begin();
//	while (it != s.end())
//	{
//		 *it += 2;
//
//		cout << *it << " ";
//		++it;
//	}
//	cout << endl;
//
//	string::reverse_iterator rit = s.rbegin();
//	while (rit != s.rend())
//	{
//		 (*rit) += 3;
//
//		cout << *rit << " ";
//		++rit;
//	}
//}
//int main()
//{
//	Func("hellow world");
//}
//void addStrings(string num1, string num2) {
//    int a, b, add=0, i = 0, j = 0, sum = 0;
//    string s;
//    a = num1.size() - 1;
//    b = num2.size() - 1;
//    while (a >= 0 || b >= 0)
//    {
//        i = a >= 0 ? num1[a] : 0;
//        j = b >= 0 ? num2[b] : 0;
//        sum = i + j + add;
//        s += '0' + sum % 10;
//        sum /= 10;
//        add = sum;
//    }
//    reverse(s.begin(), s.end());
//}
//int main()
//{
//    addStrings("999", "2");
//}
//#include<iostream>
//using namespace std;
//int main()
//{
//	string s1("hello world");
//
//	// 开空间
//	s1.reserve(100);
//	cout << s1.size() << endl;
//	cout << s1.capacity() << endl;
//
//	// 开空间+填值初始化
//	//s1.resize(200);
//	s1.resize(200, 'x');
//	cout << s1.size() << endl;
//	cout << s1.capacity() << endl;
//
//	s1.resize(20);
//	cout << s1.size() << endl;
//	cout << s1.capacity() << endl;
//
//	s1.resize(0);
//	cout << s1.size() << endl;
//	cout << s1.capacity() << endl;
//
//	return 0;
//}
//int main()
//{
//	// world替换成 xxxxxxxxxxxxxxxxxxxxxx
//	std::string str("There are two needles in this haystack with needles.");
//	std::string str2("needle");
//
//	// different member versions of find in the same order as above:
//	std::size_t found = str.find(str2);
//	if (found != std::string::npos)
//		std::cout << "first 'needle' found at: " << found << '\n';
//
//	found = str.find("needl",0,5);
//	if (found != std::string::npos)
//		std::cout << "second 'needle' found at: " << found << '\n';
////	// 所有空格替换成20%
////	string s2("hello world hello bit");
////	string s3;
////	for (auto ch : s2)
////	{
////		if (ch != ' ')
////		{
////			s3 += ch;
////		}
////		else
////		{
////			s3 += "20%";
////		}
////	}
////
////	s2 = s3;
////	cout << s2 << endl;
////	cout << s2.c_str() << endl;
////
////	// c的一些接口函数配合
////	string filename = "test.cpp";
////	filename += ".zip";
////
////	FILE* fout = fopen(filename.c_str(), "r");
////
//	return 0;
//}
//int main()
//{
//	string url = "https://legacy.cplusplus.com/reference/string/string/";
//	 协议  域名  资源名
//	size_t pos1 = url.find("://");
//	string protocol;
//	if (pos1 != string::npos)
//	{
//		protocol = url.substr(0, pos1);
//	}
//	cout << protocol << endl;
//
//	string domain;
//	string uri;
//
//	size_t pos2 = url.find('/', pos1 + 3);
//	if (pos2 != string::npos)
//	{
//		domain = url.substr(pos1 + 3, pos2 - (pos1 + 3));
//		uri = url.substr(pos2 + 1);
//	}
//	cout << domain << endl;
//	cout << uri << endl;
//	return 0;
//}
//i
//class MyClass {
//public:
//    static int staticVar; // 声明静态成员变量
//
//    // 静态成员函数，用于改变静态成员变量的值
//    static void setStaticVar(int value) {
//        staticVar = value;
//    }
//};
//
//// 初始化静态成员变量
//int MyClass::staticVar = 0;
//
//int main() {
//    MyClass::setStaticVar(10); // 通过类名直接调用静态成员函数来改变静态成员变量的值
//    std::cout << "New value of staticVar: " << MyClass::staticVar << std::endl;
//    return 0;
//}#include<iostream>
#include <iostream>
#include <string>
#include<vector>
#include<list>
#include<stack>
#include<algorithm>
#include<iostream>
using namespace std;
///*两栈实现队列*/
//class MyQueue {
//public:
//    stack<int> a;
//    stack<int> b;
//    void push(int x) {
//        while (!b.empty())
//        {
//            a.push(b.top());
//            b.pop();
//        }
//        a.push(x);
//    }
//
//    int pop() {
//        while (!b.empty())
//        {
//            b.pop();
//        }
//        while (!a.empty())
//        {
//            b.push(a.top());
//            a.pop();
//        }
//        b.pop();
//        int c = b.top();
//        while (!b.empty())
//        {
//            a.push(b.top());
//            b.pop();
//        }
//        return c;
//    }
//
//    int peek() {
//        while (!b.empty())
//        {
//            b.pop();
//        }
//        while (!a.empty())
//        {
//            b.push(a.top());
//            a.pop();
//        }
//        int c = b.top();
//        while (!b.empty())
//        {
//            a.push(b.top());
//            b.pop();
//        }
//        return c;
//    }
//
//    bool empty() {
//        return b.empty();
//    }
//};
/*逆波兰表达式*/
//class Solution {
//public:
//    int evalRPN(vector<string>& tokens) {
//        stack<int> a;
//        for (string& e : tokens)
//        {
//            if (e.size() >= 2 || e[0] >= '0')
//            {
//                a.emplace((int)stoi(e));
//            }
//            else
//            {
//                int b = a.top(); a.pop();
//                int c = a.top(); a.pop();
//                switch (e[0])
//                {
//                case '+':
//                    a.push(c + b);
//                    break;
//                case '-':
//                    a.push(c - b);
//                    break;
//                case '*':
//                    a.push(c * b);
//                    break;
//                case '/':
//                    a.push(c / b);
//                    break;
//                }
//            }
//        }
//        return a.top();
//    }
//};
//int main()
//{
//    MyQueue a;
//    a.push(1);
//    a.push(2);
//    int c=a.peek();
//    int d=a.pop();
//    bool f=a.empty();
//
//}
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
/*队列的二叉树层序遍历*/
//class Solution {
//public:
//    vector<vector<int>> levelOrder(TreeNode* root) {
//        vector<vector<int>> ret;
//        if (root == nullptr)
//        {
//            return ret;
//        }
//        queue<TreeNode*> q;
//        q.push(root);
//        while (!q.empty())
//        {
//            ret.push_back(vector<int>());
//            int levelsize = q.size();
//            for (int i = 1; i <= levelsize; i++)
//            {
//                if (q.front()->left)
//                    q.push(q.front()->left);
//                if (q.front()->right)
//                    q.push(q.front()->right);
//                ret.back().push_back(q.front()->val);
//                q.pop();
//            }
//        }
//        return ret;
//    }
//};
//int main()
//{
//    vector<int> i;
//    list<int> j;
//    for (int i = 0; i < 10; i++)
//    {
//        int a = rand();
//        j.push_back(a);
//    }
//    for (auto i : j)/*迭代器循环遍历有隐式解引用*/
//    {
//        cout << i << " ";
//    }
//    for (auto k : j)
//    {
//        i.push_back(k);
//    }
//    sort(i.begin(), i.end());
//
//}


/*调试OJ题目的测例*/
#include"vector"
//  struct TreeNode {
//      int val;
//      TreeNode *left;
//      TreeNode *right;
//      TreeNode() : val(0), left(nullptr), right(nullptr) {}
//      TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
//     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
//  };
// 
//class Solution {
//public:
//    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
//        if (preorder.size() == 0)
//        {
//            return nullptr;
//        }
//        TreeNode* root = new TreeNode;
//        root->val = preorder[0];
//        root->left = root->right = nullptr;
//        vector<int>::iterator it = find(inorder.begin(), inorder.end(), preorder[0]);
//        vector<int> pl(preorder.begin() + 1, preorder.begin() + 1 + (it - inorder.begin()));
//        vector<int> pr(preorder.begin() + 1 + (it - inorder.begin()), preorder.end());
//        vector<int> il(inorder.begin(), it);
//        vector<int> ir(it + 1, inorder.end());
//        root->left = buildTree(pl, il);
//        root->right = buildTree(pr, ir);
//        return root;
//    }
//private:
//    TreeNode* a;
//};
//int main()
//{
//    vector<int>arr;
//    int _arr[] = { 9,3,15,20,7 };
//    for (auto t : _arr)
//    {
//        arr.push_back(t);
//    }
//    vector<int>arr1;
//    int _arr1[] = { 3,9,20,15,7};
//    for (auto t : _arr1)
//    {
//        arr1.push_back(t);
//    }
//    Solution a;
//    a.buildTree(arr1, arr);
//}
//struct TreeNode {
//    int val;
//    struct TreeNode* left;
//    struct TreeNode* right;
//    TreeNode(int x) :
//        val(x), left(NULL), right(NULL) {
//    }
//}; 
//#include <cstddef>
//class Solution {
//    TreeNode* head = nullptr;
//    TreeNode* headreal = nullptr;
//public:
//    TreeNode* Convert(TreeNode* pRootOfTree) {
//        Convert(pRootOfTree);
//        return  headreal;
//    }
//private:
//    void ConnvertSub(TreeNode* pRootOfTree) {
//        if (pRootOfTree == nullptr) {
//            return;
//        }
//        ConnvertSub(pRootOfTree->left);
//        if (head == nullptr) {
//            head = pRootOfTree;
//            headreal = pRootOfTree;
//        }
//        else {
//            head->right = pRootOfTree;
//            pRootOfTree->left = head;
//            head = pRootOfTree;
//        }
//        ConnvertSub(pRootOfTree->right);
//    }
//};
//int main()
//{
//    TreeNode a(10);
//    TreeNode b(6);
//    TreeNode c(4);
//    TreeNode d(8);
//    TreeNode e(14);
//    TreeNode f(12);
//    TreeNode g(16);
//    TreeNode* k = &a;
//    a.left = &b;
//    b.left = &c;
//    b.right = &d;
//    a.right = &e;
//    e.left = &f;
//    e.right = &g;
//    Solution s;
//    s.Convert(k);
//
//}


//
//#include <stdio.h>
//#include <stdlib.h>
//#include <string.h>
//    typedef int ElemType;
//typedef int Status;
//#define ERROR 0
//#define OK 1
//
//typedef struct LNode {
//
//    ElemType data;
//    struct LNode* next;
//}LNode, * LinkList;
//
//Status GetElem_L(LinkList& L, int i, ElemType& e) {
//    LinkList p;
//    p = L->next;
//    int j = 1;
//    while (p && j < i) {
//        p = p->next;
//        ++j;
//    }
//    if (!p || j > i)
//        return ERROR;
//    e = p->data;
//    return OK;
//}
//
//Status ListInsert_L(LinkList& L, int i, ElemType e) {
//    LinkList p, q;
//    p = L;
//    int j = 0;
//    while (p && j < i - 1) {
//        p = p->next;
//        ++j;
//    }
//    if (!p || j > i - 1)
//        return ERROR;
//    q = (LinkList)malloc(sizeof(LNode));
//    q->data = e;
//    q->next = p->next;
//    p->next = q;
//    return OK;
//}
//
//Status ListDelete_L(LinkList& L, int i, ElemType& e) {
//    LinkList p, q;
//    p = L;
//    int j = 0;
//    while(p->next && j < i - 1) {
//        p = p->next;
//        ++j;
//    }
//    if (!(p->next) || j > i - 1)
//        return ERROR;
//    e = p->next->data;
//    q = p->next;
//    p->next = q->next;
//    free(q);
//    return OK;
//}
//
//void CreateList_L(LinkList& L, int n) {
//    LinkList p;
//    int i;
//    L = (LinkList)malloc(sizeof(LNode));
//    L->next = NULL;
//
//    for (i = n; i > 0; --i)
//    {
//        p = (LinkList)malloc(sizeof(LNode));
//        scanf("%d", &p->data);
//        p->next = L->next;
//        L->next = p;
//    }
//}
//
//int ShowList_L(LinkList L) {
//    int m, n = 0;
//    LinkList p;
//    p = L->next;
//    if (!p)
//        return ERROR;
//    for (m = 0; p; m++)
//    {
//        printf("%d ", (p->data));
//        p = p->next;
//        n++;
//    }
//    return n;
//}
//
//int main() {
//    int n;
//    int m;
//    char strInst[30];
//    int a;
//    LinkList L;
//    int e;
//    scanf("%d", &n);
//
//    CreateList_L(L, n);
//    scanf("%d", &m);
//    while (m--) {
//        scanf("%s", strInst);
//        if (strcmp(strInst, "get") == 0) {
//            scanf("%d", &a);
//            if (GetElem_L(L, a, e) == OK) {
//                printf("%d\n", e);
//            }
//            else {
//                puts("get fail");
//            }
//        }
//        else if (strcmp(strInst,"insert") == 0) {
//            scanf("%d%d", &a, &e);
//            if (ListInsert_L(L, a, e) == OK) {
//                puts("insert OK");
//            }
//            else {
//                puts("insert fail");
//            }
//        }
//        else if (strcmp(strInst,"show") == 0) {
//            if (ShowList_L(L) == ERROR) {
//                puts("Link list is empty");
//            }
//        }
//    }
//    return 0;
//}

//map解决括号匹配问题
//#include<map>
//class Solution {
//public:
//    bool isValid(string s) {
//        stack<char> it;
//        map<char, char> mapit;
//        mapit['('] = ')';
//        mapit ['['] = ']';
//        mapit['{'] = '}';
//        for (auto it_s : s)
//        {
//            if (mapit.count(it_s))
//            {
//                it.push(it_s);
//            }
//            char its = it.top();
//            if (mapit[its] == it_s)
//            {
//                it.pop();
//            }
//        }
//        if (it.size())
//        {
//            return false;
//        }
//        else
//            return true;
//        }
//};


//前K个高频单词
//#include<vector>
//#include<map>
//struct Greet
//{
//    bool operator()(const pair<string, int>& a, const pair<string, int>& b)
//    {
//        return a.second > b.second || (a.second == b.second && a.first < b.first);
//    }
//};
//vector<string> topKFrequent(vector<string>& words, int k) {
//    map<string, int> kv;
//    for (const auto& e : words)
//    {
//        kv[e]++;
//    }
//    vector<pair<string, int>> kv_vector(kv.begin(), kv.end());
//    sort(kv_vector.begin(), kv_vector.end(), Greet());
//    vector<string> kvstring;
//    for (auto i : kv_vector)
//    {
//        kvstring.push_back(i.first);
//        k--;
//        if (k == 0)
//        {
//            break;
//        }
//    }
//    return kvstring;
//}
#define _CRT_SECURE_NO_WARNINGS 1 
#include<iostream>
#include<vector>
using namespace std;
template<class T>
struct Less
{
	bool operator()(const T& x, const T& y)
	{
		return x < y;
	}
};
template<class T>
struct Greater
{
	bool operator()(const T& x, const T& y)
	{
		return x > y;
	}
};
//仿函数小于和大于的实现
template<class T, class Container = vector<T>, class Compare = Less<T>>
class priority_queue
{
public:
	void Adjustup(int child)
	{
		Compare com;
		int parent = (child) / 2;
		while (child > 0)
		{
			if (com(_con[parent], _con[child]))
			{
				swap(_con[child], _con[parent]);
				child = parent;
				parent = (child - 1) / 2;
			}
			else
			{
				break;
			}
		}
	}
	void Adjustdown(int parent)
	{
		Compare com;
		int child = parent * 2 + 1;
		while (child < _con.size())
		{
			if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
			{
				child++;
			}
			if (com(_con[parent], _con[child]))
			{
				swap(_con[child], _con[parent]);
				parent = child;
				child = parent * 2 + 1;
			}
			else
			{
				break;
			}
		}
	}
	void push(const T& x)
	{
		_con.push_back(x);
		Adjustup(_con.size() - 1);
	}
	void pop()
	{
		swap(_con[0], _con[_con.size() - 1]);
		_con.pop_back();
		Adjustdown(0);
	}
	T top()
	{
		return _con[0];
	}
	size_t size()
	{
		return _con.size();
	}
	bool empty()
	{
		return _con.empty();
	}
private:Container _con;
};
int main()
{
	priority_queue<int, vector<int>, Greater<int>> pq;
	//bit::priority_queue<int> pq;
	pq.push(4);
	pq.push(1);
	pq.push(5);
	pq.push(7);
	pq.push(9);
	while (!pq.empty())
	{
		cout << pq.top() << " ";
		pq.pop();
	}
	cout << endl;

	return 0;
}
